package com.hp.test.interview.dynamic;

import java.util.Arrays;

/**
 * http://www.geeksforgeeks.org/dynamic-programming-set-20-maximum-length-chain-of-pairs/
 */
public class MaximumLengthChainPair {

    public static void main(String args[]) {
        Pair p = new Pair(5, 7);
        Pair p1 = new Pair(2, 3);
        Pair p2 = new Pair(2, 6);
        Pair p3 = new Pair(9, 11);
        Pair p4 = new Pair(8, 10);
        Pair p5 = new Pair(11, 14);

        Pair[] arr = {p, p1, p2, p3, p4, p5};
        MaximumLengthChainPair mlcp = new MaximumLengthChainPair();
        int r = mlcp.maxLength(arr);
        System.out.print(r);
    }

    public int maxLength(Pair[] arr) {
        Arrays.sort(arr);

        int T[] = new int[arr.length + 1];
        for (int i = 0; i < T.length; i++) {
            T[i] = 1;
        }
        for (int i = 2; i < T.length; i++) {
            for (int j = 1; j < i; j++) {
                if (arr[j - 1].b < arr[i - 1].a) {
                    T[i] = Math.max(T[j] + 1, T[i]);
                }
            }
        }

        int max = 0;
        for (int i = 1; i < T.length; i++) {
            if (max < T[i]) {
                max = T[i];
            }
        }
        return max;
    }

    static class Pair implements Comparable<Pair> {
        int a;
        int b;
        public Pair(int a, int b) {
            this.a = a;
            this.b = b;
        }

        @Override
        public int compareTo(Pair o) {
            if (this.a <= o.a) {
                return -1;
            } else {
                return 1;
            }
        }
    }
}
